package com.lft.graph01.create_graph;

import java.lang.reflect.Array;

/**
 * 无向图的实现——邻接表
 */
public class GraphAdjacencyList<E> implements GraphInterface<E> {
	/**
	 * 邻接表中对就的链表的顶点
	 */
	private static class EdgeNode {
		/**
		 * 邻接顶点的索引
		 */
		int adjVertexIndex;
		
		/**
		 * 存储边或弧相关的信息，如权值。
		 */
		int weight;
		
		/**
		 * 该顶点的下一个邻接头顶点
		 */
		EdgeNode nextAdjNode;
		
		/**
		 * 构造器，初始化当前节点的 索引，权重值。
		 * @param adjVertexNo
		 * @param weight
		 */
		public EdgeNode(int adjVertexNo, int weight) {
			this.adjVertexIndex = adjVertexNo;
			this.weight = weight;
		}
	}
	
	/**
	 * 邻接表中表的顶点。
	 * @param <E>
	 */
	private static class VertexNode<E> {
		/**
		 * 顶点数据信息
		 */
		E data;
		
		/**
		 * 邻接表的第1个顶点
		 */
		EdgeNode firstAdj;
	}
	
	/**
	 * 顶点数组
	 */
	private VertexNode<E>[] vertexs;
	/**
	 * 顶点的实际数量。
	 */
	private int numOfVertexs;
	
	/**
	 * 顶点的最大数量。
	 */
	private int maxNumOfVertexs;
	
	/**
	 * 判断顶点是否被访问过。true：访问过；false：未访问过。
	 */
	private boolean[] visited;
	
	public GraphAdjacencyList(int maxNumOfVertexs) {
		this.maxNumOfVertexs = maxNumOfVertexs;
		vertexs = (VertexNode<E>[]) Array.newInstance(VertexNode.class, maxNumOfVertexs);
	}
	
	/**
	 * 获取顶点的个数。
	 * @return
	 */
	@Override
	public int getNumOfVertex() {
		return numOfVertexs;
	}
	
	/**
	 * 插入顶点
	 * @param v
	 * @return
	 */
	@Override
	public boolean insertVertex(E v) {
		if (numOfVertexs >= maxNumOfVertexs) {
			return false;
		}
		VertexNode<E> vertex = new VertexNode<>();
		vertex.data = v;
		vertexs[numOfVertexs++] = vertex;
		return true;
	}
	
	/**
	 * 删除顶点
	 * @param v 要删除顶点的数据
	 * @return
	 */
	@Override
	public boolean deleteVertex(E v) {
		// 遍历顶点数组。
		for (int i = 0; i < numOfVertexs; i++) {
			// 如果当前顶点数组的值跟要查找的值相等。找到了要删除的顶点
			if (vertexs[i].data.equals(v)) {
				// 循环将要删除顶点后面的顶点往前移覆盖要删除的顶点。
				for (int j = i; j < numOfVertexs - 1; j++) {
					vertexs[j] = vertexs[j + 1];
				}
				// 将最后一项顶点置空。
				vertexs[numOfVertexs - 1] = null;
				// 顶点数量减1
				numOfVertexs--;
				// 临时顶点cur,表示当前顶点。
				EdgeNode cur;
				// 临时顶点pre,表示当前顶点的前一个顶点。
				EdgeNode pre;
				// 遍历每一个顶点，将顶点表中的每个顶点的第一个邻接顶点的索引是删除顶点索引的都删除。
				for (int j = 0; j < numOfVertexs; j++) {
					// 如果当前顶点没有邻接头顶点。
					if (vertexs[j].firstAdj == null) {
						// 继续往后查找删除。
						continue;
					}
					// 如果当前顶点的邻接的对头顶点的索引正好是 删除顶点的索引。
					if (vertexs[j].firstAdj.adjVertexIndex == i) {
						// 将邻接头顶点置空。不指向删除的顶点。
						vertexs[j].firstAdj = null;
						// 继续往后查找删除。
						continue;
					}
					// 将临时指针指向当前顶点的邻接头顶点。
					cur = vertexs[j].firstAdj;
					//循环遍历邻接顶点的链表。
					while (cur != null) {
						// 先将 前一个头顶点指向 cur.
						pre = cur;
						// 将 cur 指向 后一个头顶点。
						cur = cur.nextAdjNode;
						// 如果 cur 不为空。且 cur的邻接头顶点的索引 正好是要删除顶点的索引。
						if (cur != null && cur.adjVertexIndex == i) {
							// 将 pre 顶点的邻接头顶点 指向 cur 顶点的邻接头顶点。
							pre.nextAdjNode = cur.nextAdjNode;
							// 跳出当前while循环。
							break;
						}
					}
				}
				// 遍历每一个顶点，删除了那个顶点后，其他在删除顶点后的顶点索引要前移。
				for (int j = 0; j < numOfVertexs; j++) {
					// cur 指向当前顶点的邻接头顶点。
					cur = vertexs[j].firstAdj;
					// 循环遍历
					while (cur != null) {
						// 只要cur的邻接头顶点的索引 > 删除的顶点的索引
						if (cur.adjVertexIndex > i) {
							// 将索引-1
							cur.adjVertexIndex--;
						}
						// 后移继续遍历
						cur = cur.nextAdjNode;
					}
				}
				// 操作完之后表示删除顶点成功。
				return true;
			}
		}
		return false;
	}
	
	/**
	 * 定位顶点的位置
	 * @param v 要查找的顶点。
	 * @return -1 未找到。其他值就是顶点的索引。
	 */
	@Override
	public int indexOfVertex(E v) {
		// 循环遍历
		for (int i = 0; i < numOfVertexs; i++) {
			// 当前顶点的数据 == 要查找的数据
			if (vertexs[i].data.equals(v)) {
				// 返回当前索引
				return i;
			}
		}
		// 没找到 返回-1
		return -1;
	}
	
	/**
	 * 查找指定位置的顶点的值
	 * @param vertexIndex
	 * @return
	 */
	@Override
	public E valueOfVertex(int vertexIndex) {
		if (vertexIndex < 0 || vertexIndex > numOfVertexs) {
			return null;
		}
		return vertexs[vertexIndex].data;
	}
	
	/**
	 * 插入边
	 * @param vertexIndex1 顶点1索引
	 * @param vertexIndex2 顶点2索引
	 * @param weight       权重 1表示连接。0表示不通。
	 * @return
	 */
	@Override
	public boolean insertEdge(int vertexIndex1, int vertexIndex2, int weight) {
		if (vertexIndex1 < 0 || vertexIndex1 >= numOfVertexs || vertexIndex2 < 0 || vertexIndex2 >= numOfVertexs) {
			throw new ArrayIndexOutOfBoundsException();
		}
		if (weight == 0) {
			return false;
		}
		// 无向图，先往 vertexIndex1 索引的顶点 插入 vertexIndex2 索引的顶点。
		// 用 vertexIndex2 索引 和 weight 权重 创建一个临时 顶点。
		EdgeNode vertex1 = new EdgeNode(vertexIndex2, weight);
		// 如果 vertexIndex1 索引的顶点 没有邻接顶点。
		if (vertexs[vertexIndex1].firstAdj == null) {
			// 直接将要插入的 vertex1 放在 vertexIndex1 顶点的邻接头顶点位置上。
			vertexs[vertexIndex1].firstAdj = vertex1;
		}
		// 如果 vertexIndex1 索引的顶点 有邻接顶点。
		else {
			// 采用头插法。将原来的邻接头顶点赋值给 新顶点
			vertex1.nextAdjNode = vertexs[vertexIndex1].firstAdj;
			// 再将新顶点赋值给 vertexIndex1 顶点的邻接头顶点。
			vertexs[vertexIndex1].firstAdj = vertex1;
		}
		
		// 再往 vertexIndex2 索引的顶点 插入 vertexIndex1 索引的顶点。
		EdgeNode vertex2 = new EdgeNode(vertexIndex1, weight);
		// 如果 vertexIndex2 索引的顶点 没有邻接顶点。
		if (vertexs[vertexIndex2].firstAdj == null) {
			// 直接将要插入的 vertex2 放在 vertexIndex2 顶点的邻接头顶点位置上。
			vertexs[vertexIndex2].firstAdj = vertex2;
		}
		// 如果 vertexIndex2 索引的顶点 有邻接顶点。
		else {
			// 采用头插法。
			// 将原来的邻接头顶点赋值给 新顶点
			vertex2.nextAdjNode = vertexs[vertexIndex2].firstAdj;
			// 再将新顶点赋值给 vertexIndex2 顶点的邻接头顶点。
			vertexs[vertexIndex2].firstAdj = vertex2;
		}
		return true;
	}
	
	/**
	 * 删除边
	 * @param vertexIndex1 顶点1索引
	 * @param vertexIndex2 顶点2索引
	 * @return
	 */
	@Override
	public boolean deleteEdge(int vertexIndex1, int vertexIndex2) {
		if (vertexIndex1 < 0 || vertexIndex1 >= numOfVertexs || vertexIndex2 < 0 || vertexIndex2 >= numOfVertexs) {
			throw new ArrayIndexOutOfBoundsException();
		}
		// 删除索引为index1的顶点与索引为index2的顶点之间的边
		EdgeNode cur = vertexs[vertexIndex1].firstAdj;
		EdgeNode pre = null;
		// 删除索引为 vertexIndex1 的顶点与索引为 vertexIndex2 的顶点之间的边
		while (cur != null && cur.adjVertexIndex != vertexIndex2) {
			pre = cur;
			cur = cur.nextAdjNode;
		}
		if (cur != null) {
			pre.nextAdjNode = cur.nextAdjNode;
		}
		
		// 删除索引为 vertexIndex2 的顶点与索引为 vertexInde1 的顶点之间的边
		cur = vertexs[vertexIndex2].firstAdj;
		while (cur != null && cur.adjVertexIndex != vertexIndex1) {
			pre = cur;
			cur = cur.nextAdjNode;
		}
		if (cur != null) {
			pre.nextAdjNode = cur.nextAdjNode;
		}
		return true;
	}
	
	/**
	 * 查找顶点1与顶点2边的权值
	 * @param vertexIndex1 顶点1索引
	 * @param vertexIndex2 顶点2索引
	 * @return
	 */
	@Override
	public int getEdge(int vertexIndex1, int vertexIndex2) {
		if (vertexIndex1 < 0 || vertexIndex1 >= numOfVertexs || vertexIndex2 < 0 || vertexIndex2 >= numOfVertexs) {
			throw new IndexOutOfBoundsException();
		}
		EdgeNode cur = vertexs[vertexIndex1].firstAdj;
		while (cur != null) {
			if (cur.adjVertexIndex == vertexIndex2) {
				return cur.weight;
			}
			cur = cur.nextAdjNode;
		}
		return 0;
	}
}
